package com.kehao.leetcode.algorithm;

import org.junit.Test;

//https://leetcode-cn.com/problems/house-robber/
public class Solution198 {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length+1];//dp[i] 代表偷前i家房，赚到的钱数
        dp[0] = 0; //捕头
        dp[1] = nums[0];
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        return dp[dp.length-1];
    }

    @Test
    public void myTest1(){
        int[] nums = new int[]{1,2,3,1};
        System.out.println(rob(nums));
    }

    @Test
    public void myTest2(){
        int[] nums = new int[]{2,7,9,3,1};
        System.out.println(rob(nums));
    }
}
